package com.wc.算法提高课.A第一章_动态规划.斜率优化DP.运输小猫;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/5/14 21:24
 * @description https://www.acwing.com/problem/content/305/
 */
public class Main {
    /**
     * 思路:
     * d[i] 表示从0到第i座山的距离
     * a[i] 表示到达第h坐山接第i只猫的最短时间
     * a[i] = t[i] - d[h]
     * s[i] 表示a[i]的前缀和
     * f[j][i] 表示j个饲养员已经取了前i只猫的最小时间
     * 假设上一次的分割点为k
     * 那就说明
     * f[j][i] = f[j - 1][k] + a[i] * (i - k) - (s[i] - s[k])
     * 变形
     * f[j - 1][k] + s[k] = a[i] * k + f[j][i] - a[i] * i + s[i]
     * <p>
     * a[i] 单调递增， k单调递增, 将y = f[j - 1][k] + s[k], x = k,就可以运用斜率优化
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 100010, M = 100010, P = 110;
    static long INF = 0x3f3f3f3fL * 0x3f3f3f3f;
    static int[] d = new int[N], t = new int[N];
    // a[i] = t[i] - d[i]
    static long[] a = new long[N];
    static long[] s = new long[N];
    static long[][] f = new long[P][M];
    static int[] q = new int[M];
    static int n, m, p;

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        p = sc.nextInt();
        for (int i = 2; i <= n; i++) {
            d[i] = sc.nextInt();
            d[i] += d[i - 1];
        }
        for (int i = 1; i <= m; i++) {
            int h = sc.nextInt();
            t[i] = sc.nextInt();
            a[i] = (long) t[i] - d[h];

        }
        Arrays.sort(a, 1, m + 1);
        for (int i = 1; i <= m; i++) {
            s[i] = s[i - 1] + a[i];
        }
        // f[i][0] i 个饲养员 取0个猫, 不需要等待时间
        for (int i = 0; i <= p; i++) {
            Arrays.fill(f[i], 1, m + 1, INF);
        }

        for (int j = 1; j <= p; j++) {
            int hh = 1, tt = 0;
            q[++tt] = 0;
            for (int i = 1; i <= m; i++) {
                // 去除前面的凸包, 这里注意一定需要用后面的点减去前面的点, 因为后面的点一定比前面的这个点高, 否则移项的时候是负数, 需要改变符号
                while (hh < tt && (getY(q[hh + 1], j) - getY(q[hh], j)) <=
                        a[i] * (q[hh + 1] - q[hh])) hh++;
                int k = q[hh];
                f[j][i] = f[j - 1][k] + a[i] * (i - k) - (s[i] - s[k]);
                // 将f[j][i] 插入
                while (hh < tt && (getY(q[tt], j) - getY(q[tt - 1], j)) * (i - q[tt]) >=
                        (getY(i, j) - getY(q[tt], j)) * (q[tt] - q[tt - 1])) tt--;
                q[++tt] = i;
            }
        }
        out.println(f[p][m]);
        out.flush();
    }

    static long getY(int k, int j) {
        return f[j - 1][k] + s[k];
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
